#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#include <immintrin.h>
//#include <emmintrin.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define fi first
#define se second
#define pii pair<int,int>
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
const int base2=1000033,Mod2=1e9+7;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int n,C;
int a[N];
int dp[N];
int qzh[N];
int f[100005][105];
int p[N];
inline int work(int x,int y){
	if(y>=x) return y-x;
	return C;
}
signed main(){
	freopen("minimize.in","r",stdin);
	freopen("minimize.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	n=read(),C=read();int mx=0; 
	For(i,1,n) a[i]=read(),mx=max(mx,a[i]);
	if(C==0){
		puts("0");
		return 0;
	}bool flag=0;
	For(i,1,n-1){
		if(a[i]<=a[i+1]);else flag=1;
	}
	if(!flag){
		int ans=n*C,ss=0;
		For(i,1,n){
			ss+=a[i];
			ans=min(ans,i*a[i]-ss+(n-i)*C);
		}printf("%lld\n",ans);
		return 0;
	}
	if(n<=1000){
		memset(dp,0x3f,sizeof(dp));
		dp[0]=0;
		int ans=1e16;
		For(i,1,n){
			int ss=0;
			For(j,1,i-1){
				if(a[i]>=a[j])ss+=a[i]-a[j];
				else ss+=C;
			}
			dp[i]=min(dp[i],ss);
		}
		For(i,0,n){
			int ss=0;
			qzh[i]=0;
			For(j,i+1,n){
				if(a[j]<=a[i])dp[j]=min(dp[i]+ss,dp[j]);
				int pp=0;
				if(a[j]<=a[i]){
					Rof(t,j-1,i+1){
						pp+=work(a[t],a[j]);
						dp[j]=min(dp[i]+pp+qzh[t-1],dp[j]);
					}
				}ss+=work(a[j],a[i]);
				qzh[j]=ss; 
				if(j==n)ans=min(ans,dp[i]+ss); 
			}
		}
		printf("%lld\n",min(ans,dp[n]));
		return 0;
	}
	if(mx<=100){
		memset(f,0x3f,sizeof(f));
	 f[0][100]=0;
	 	For(i,1,n)Rof(j,100,0){
	 		f[i][j]=min(f[i][j],f[i-1][j]+work(a[i],j));
	 		f[i][j]=min(f[i][j],f[i][j+1]-work(a[i],j+1)+work(a[i],j));
		}
		int ans=1e16;
		For(j,0,100)ans=min(ans,f[n][j]);
		printf("%lld\n",ans);
	 	return 0;
	}
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

